package LeetCode;

/*
200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

        岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

        此外，你可以假设该网格的四条边均被水包围。



        示例 1：

        输入：grid = [
        ["1","1","1","1","0"],
        ["1","1","0","1","0"],
        ["1","1","0","0","0"],
        ["0","0","0","0","0"]
        ]
        输出：1
        示例 2：

        输入：grid = [
        ["1","1","0","0","0"],
        ["1","1","0","0","0"],
        ["0","0","1","0","0"],
        ["0","0","0","1","1"]
        ]
        输出：3


        提示：

        m == grid.length
        n == grid[i].length
        1 <= m, n <= 300
        grid[i][j] 的值为 '0' 或 '1'
*/

/**
 * 解决岛屿数量问题的解决方案
 * 计算给定网格中的岛屿数量
 * 岛屿被水包围，由水平或垂直连接的陆地组成
 * 该类提供了一个使用深度优先搜索（DFS）解决问题的方法
 */
public class Code200_numIslands {

    /**
     * 计算给定网格中的岛屿数量
     *
     * @param grid 二维网格，其中 '1' 表示陆地，'0' 表示水
     * @return 岛屿的数量
     */
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 使用深度优先搜索（DFS）标记与当前陆地相连的所有陆地
     *
     * @param grid 二维网格
     * @param i 当前行索引
     * @param j 当前列索引
     */
    private void dfs(char[][] grid, int i, int j) {
        // 判断边界条件
        if (!inArea(i, j, grid) || grid[i][j] != '1') {
            return;
        }
        // 标记当前已遍历，防止重复遍历
        grid[i][j] = '2';
        // 深度搜索上下左右
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }

    /**
     * 检查给定坐标是否在网格范围内
     *
     * @param i 行索引
     * @param j 列索引
     * @param grid 二维网格
     * @return 如果坐标在网格范围内返回 true，否则返回 false
     */
    private boolean inArea(int i, int j, char[][] grid) {
        if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) {
            return true;
        }
        return false;
    }

    /**
     * 主方法，用于测试 numIslands 方法
     *
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        char[][] c = new char[][]{
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
        Code200_numIslands code200_numIslands = new Code200_numIslands();
        System.out.println(code200_numIslands.numIslands(c));
    }
}

